|
In graph theory, a connected graph ''G'' is said to be ''k''-vertex-connected (or ''k''-connected) if it has more than ''k'' vertices and remains connected whenever fewer than ''k'' vertices are removed. The vertex-connectivity, or just connectivity, of a graph is the largest ''k'' for which the graph is ''k''-vertex-connected. == Definitions == A graph (other than a complete graph) has connectivity ''k'' if ''k'' is the size of the smallest subset of vertices such that the graph becomes disconnected if you delete them. Complete graphs are not included in this version of the definition since they cannot be disconnected by deleting vertices. The complete graph with ''n'' vertices has connectivity ''n'' − 1, as implied by the first definition. An equivalent definition is that a graph with at least two vertices is ''k''-connected if, for every pair of its vertices, it is possible to find ''k'' vertex-independent paths connecting these vertices; see Menger's theorem . This definition produces the same answer, ''n'' − 1, for the connectivity of the complete graph ''K''''n''.〔 A 1-connected graph is called connected; a 2-connected graph is called biconnected. A 3-connected graph is called triconnected. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-vertex-connected graph」の詳細全文を読む スポンサード リンク
|